import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int m = 0, n = 0;
    static Queue<int[]> q = new LinkedList<>();

    public static int maxAreaOfIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        //用来标记grid中的元素是否被遍历到
        boolean[][] temp = new boolean[m][n];

        int maxArea = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !temp[i][j]) {
                    //bfs
                    maxArea = Math.max(bfs(grid, temp, i, j), maxArea);
                }
            }
        }

        return maxArea;
    }

    public static int bfs(int[][] grid, boolean[][] temp, int i, int j) {
        int max = 0;
        q.offer(new int[]{i, j});
        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int x = arr[0];
            int y = arr[1];
            System.out.println(x + ", " + y);
            temp[x][y] = true;
            max++;
            //遍历四个方向
            for (int k = 0; k < 4; k++) {
                int xx = x + dx[k];
                int yy = y + dy[k];
                if (xx >= 0 && yy >= 0 && xx < m && yy < n && !temp[xx][yy] && grid[xx][yy] == 1) {
                    q.offer(new int[]{xx, yy});
                    temp[xx][yy] = true;
                }
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(maxAreaOfIsland(new int[][]{{1,1,0,0,0}, {1,1,0,0,0}, {0,0,0,1,1}, {0,0,0,1,1}}));
    }
}
